package com.gorkr.hot100.medium;

import org.junit.jupiter.api.Test;

/**
 * @author 张心宇 <zhangxinyu20@kuaishou.com>
 * Created on 2023-01-09
 */
public class M208Trie {

    private M208Trie[] children;
    private boolean isEnd;

    public M208Trie() {
        children = new M208Trie[26];
        isEnd = false;
    }

    public void insert(String word) {
        M208Trie node = this;
        for (int i = 0; i < word.length(); i++) {
            char c = word.charAt(i);
            int index = c - 'a';
            if(node.children[index]==null){
                node.children[index] = new M208Trie();
            }
            node = node.children[index];
        }
        node.isEnd = true;
    }

    public boolean search(String word) {
        M208Trie node = this;
        for (int i = 0; i < word.length(); i++) {
            char c = word.charAt(i);
            int index = c - 'a';
            if(node.children[index]==null){
                return false;
            }
            node = node.children[index];
        }
        if(!node.isEnd){
            return false;
        }
        return true;
    }

    public boolean startsWith(String prefix) {
        M208Trie node = this;
        for (int i = 0; i < prefix.length(); i++) {
            char c = prefix.charAt(i);
            int index = c - 'a';
            if(node.children[index]==null){
                return false;
            }
            node=node.children[index];
        }
        return true;
    }

    @Test
    void test(){
        M208Trie m208Trie = new M208Trie();
        m208Trie.insert("apple");
        m208Trie.search("apple");
        m208Trie.search("app");
        m208Trie.startsWith("app");
        m208Trie.insert("app");
        m208Trie.search("app");


    }

}
